﻿#include<stdio.h>
#include<stdlib.h>
#define maxVertices 30
#define maxEdges 900
#define maxWeight 32767
#define impossibleValue '#'
#define impossibleWeight -1


//邻接矩阵
typedef char Type;
typedef int Weight;
typedef struct {
	int numVertices, numEdges;
	Type VerticesList[maxVertices];
	Weight Edge[maxVertices][maxVertices];
}MGraph;


int getVertexPos(MGraph& G, Type x)
{
	for (int i = 0; i < G.numVertices; i++)
	{
		if (G.VerticesList[i] == x)
		{
			return i;
		}
	}
	return -1;
}

Type getValue(MGraph& G, int v)
{
	if (v != -1)
	{
		return G.VerticesList[v];
	}
	return impossibleValue;
}

int firstNeighbor(MGraph& G, int v)
{
	if (v != -1)
	{
		for (int j = 0; j < G.numVertices; j++)
		{
			if (G.Edge[v][j] > 0 && G.Edge[v][j] < maxWeight)
			{
				return j;
			}
		}
	}
	return -1;
}


int nextNeighbor(MGraph& G, int v, int w)
{
	if (v != -1 && w != -1)
	{
		for (int j = w + 1; j < G.numVertices; j++)
		{
			if (G.Edge[v][j] > 0 && G.Edge[v][j] < maxWeight)
			{
				return j;
			}
		}
	}
	return -1;
}

Weight getWeight(MGraph& G, int v,int w)
{
	if (v != -1 && w != -1)
	{
		return G.Edge[v][w];
	}
	return impossibleWeight;
}

void createMGraph(MGraph& G, Type v[], int n, Type ed[][2], Weight c[], int e, int d)
{
	//d=1为有向图，d=0为无向图
	G.numVertices = n;
	G.numEdges = e;
	//初始化
	for (int i = 0; i < G.numVertices; i++)
	{
		G.VerticesList[i] = v[i];
		for (int j = 0; j < G.numVertices; j++)
		{
			G.Edge[i][j] = (i == j) ? 0 : maxWeight;
		}
	}

	for (int k = 0; k < G.numEdges; k++)
	{
		int i = getVertexPos(G, ed[k][0]);
		int j = getVertexPos(G, ed[k][1]);
		G.Edge[i][j] = c[k];
		if (d == 0)
		{
			G.Edge[j][i] = c[k];
		}
	}
}

void printMGraph(MGraph& G, int d)
{
	int n = G.numVertices;
	int e = G.numEdges;
	printf("顶点数%d，边数%d\n", n, e);
	int i, j, w;
	for (i = 0; i < n; i++)
	{
		int s = (d == 0) ? i : 0;
		for (int j = s; j < n; j++)
		{
			w = G.Edge[i][j];
			if (w > 0 && w < maxWeight)
			{
				printf("(%d,%d) %d", i, j, w);
			}
		}
	}
}



//深度优先搜索DFS
void DFS_recur(MGraph& G, int v, int visited[])
{
	printf("->%c", getValue(G, v));
	visited[v] = 1;
	for (int w = firstNeighbor(G, v); w != -1; w = nextNeighbor(G, v, w))
	{
		if (!visited[w])
		{
			DFS_recur(G, w, visited);
		}
	}
}

void DFS_Travelsal(MGraph& G, int v)
{
	int n = G.numVertices;
	int i;
	int visited[maxVertices];
	for (i = 0; i < n; i++)
	{
		visited[i] = 0;
	}
	DFS_recur(G, v,visited);
	printf("\n");
}


//利用DFS遍历非连通图的联通分量
void calcComponents(MGraph& G)
{
	int n = G.numVertices;
	int* visited = (int*)malloc(n*sizeof(int));
	for (int i = 0; i < n; i++)
	{
		visited[i] = 0;
	}
	int k = 0;
	for (int i = 0; i < n; i++)
	{
		if (!visited[i])
		{
			printf("输出第%d个连通分量的边\n", ++k);
			DFS_recur(G, i, visited);
			printf("\n");
		}
	}
	free(visited);
}


int main()
{
	MGraph G;
	Type vertices[] = { 'A','B','C','D' };
	int numVertices = sizeof(vertices) / sizeof(vertices[0]);

	Type edges[][2] = {
		{'A','B'},
		{'A','C'},
		{'B','C'},
		{'B','D'},
		{'C','D'}
	};

	int numEdges = sizeof(edges) / sizeof(edges[0]);
	Weight weights[] = { 1,2,3,4,5 };

	createMGraph(G, vertices, numVertices, edges, weights, numEdges, 0);
	printf("无向图\n");
	printMGraph(G, 0);

	createMGraph(G, vertices, numVertices, edges, weights, numEdges, 1);
	printf("有向图\n");
	printMGraph(G, 1);

	printf("\n");
	DFS_Travelsal(G, 0);
	calcComponents(G);
	return 0;
}